package com.g03.qt;

public class AddNum {
    public static void main(String[] args) {
        int[] arr = new int[10];
        int size = 4;
        for (int i = 1; i < 5; i++) {
            arr[i - 1] = i;
        }

        // 尾巴插入
        int flag = addOrderNum(arr, size, 10);
        if (flag > -1) {
            size++;
        }
        flag = addOrderNum(arr, size, 18);
        if (flag > -1) {
            size++;
        }
        System.out.println("尾巴插入:");
        show(arr, size);

        // 中间插入
        flag = addOrderNum(arr, size, 7);
        if (flag > -1) {
            size++;
        }
        System.out.println("中间插入:");
        show(arr, size);

        // 首部插入
        flag = addOrderNum(arr, size, -6);
        if (flag > -1) {
            size++;
        }
        System.out.println("首部插入:");
        show(arr, size);
    }


    static int addOrderNum(int[] arr, int size, int element) {
        // 有序数组的插入
        if (size >= arr.length) {
            return -1;
        }

        // 从后往前比较进行插入
        int i = size - 1;
        while (i >= 0) {
            if (arr[i] <= element) {
                arr[i + 1] = element;
                return i + 1;
            } else {
                arr[i + 1] = arr[i];
            }
            i--;
        }

        // 通过 while 循环从后往前都没有找到位置插入，则位置在首位
        arr[0] = element;
        return 0;
    }

    static void show(int[] arr, int size) {
        for (int i = 0; i < size; i++) {
            System.out.printf("%d ", arr[i]);
        }
        System.out.println();  // 打印一个换行
    }
}
